#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//定义链式队列的元素类型
typedef int DataType;

//定义链式队列的节点
typedef struct {
    DataType  data;
    struct  Node *next;
}QueueNode;

//定义链式队列
typedef struct {
    QueueNode  *front,*rear;
}LinkQueue;

//初始化
void initQueue(LinkQueue *q) {
    q->front = q->rear = NULL;
}

//判断队列是否为空
bool isEmpty(LinkQueue *q){
    return q->front == NULL && q ->rear ==NULL;
}

//打印队列
void printfQueue(LinkQueue *q){
    if(isEmpty(q)){
        printf("这是空队列\n");
        return;
    }
    printf("队列元素: ");
    QueueNode *temp;
    temp = q->front;
    while(temp != NULL){
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

//入队
void pushQueue(LinkQueue *q, DataType x) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if(newNode == NULL){
        printf("新节点内容分配失败");
    }
    if(isEmpty(q)){
        q->front = q->rear = newNode;
    }
    newNode -> data = x;
    newNode -> next = NULL;
    q->rear->next = newNode;
    q->rear = newNode;
}

// 出队
void popQueue(LinkQueue *q){
    if(isEmpty(q)){
        printf("这是一个空队列");
        return;
    }
    QueueNode *temp;
    temp = q->front;
    q->front = temp ->next;
    if(q->rear == temp){
        q->rear =NULL;
    }
    free(temp);
}


int main(){
    // 设置控制台为UTF-8编码
    #ifdef _WIN32
        system("chcp 65001 > null");
    #endif

    LinkQueue q;

    //初始化
    initQueue(&q);

    //入队
    pushQueue(&q,13);
    pushQueue(&q,45);
    pushQueue(&q,56);

    //打印队列
    printfQueue(&q);

    //出队
    popQueue(&q);

    printf("\n");
    //打印队列
    printfQueue(&q);

    return 0;
}